|
Algoritmy třídění
Schwarz, Jakub ; Smrž, Jaroslav (oponent) ; Dvořák, Jiří (vedoucí práce)
Pri obrovských objemech dat, které se behem výrobních procesu zpracovávají, je snadná orientace a hledání v nich zcela zásadní. Správné a rychlé trídení dat je jednou z nejduležitejších cinností pri jejich zpracování. Cílem této bakalárské práce je provést rešerši algoritmu trídení. K tomuto cíli budou vymezeny základní pojmy v oblasti trídení a popsáno rozdelení trídicích algoritmu podle ruzných kritérií. U každého z vybraných algoritmu vnitrního trídení polí bude analyzován princip trídení a proveden rozbor casové efektivnosti. Výsledky budou overeny experimentálním programem.
|
|
Automatické umísťování uzlů v acyklickém orientovaném grafu do GUI
Juda, Jan ; Křivka, Zbyněk (oponent) ; Kolář, Dušan (vedoucí práce)
Cílem této práce je vytvořit aplikaci pro automatické rozmísťování uzlů v acyklických orientovaných grafech. Práce se především zaměřuje na pokročilé možnosti při tvorbě umístění uzlů, z kterých za zmínku stojí výběr polohy vybraných uzlů, rozdělení grafu na podgrafy či podporu polygonálních uzlů. V řešení jsou popsány vybrané algoritmy, které jsou použity ve výsledné aplikaci, a to konkrétně Fruchterman-Reingoldův silou orientovaný algoritmus, algoritmus Kamada-Kawai a algoritmus založený na Meyerových metodách samo-organizujících se grafů.
|
|
Komprese DNA sekvencí
Friedrich, Tomáš ; Burgetová, Ivana (oponent) ; Martínek, Tomáš (vedoucí práce)
Vzrůstající objem biologických dat vyžaduje hledání nových způsobů uložení těchto dat v genetických bankách. Cílem této práce je navržení a implementace nového algoritmu pro kompresi DNA sekvencí, který je založen na porovnání DNA sekvencí s referenčním modelem a následném uložení rozdílů oproti danému referenčnímu modelu. Práce obsahuje základní znalosti z molekulární biologie potřebné k pochopení principu algoritmu. Dále vysvětluje problematiku zarovnávání a uvádí některé kompresní algoritmy vhodné pro uložení rozdílů oproti referenčnímu modelu. Práce pokračuje popisem implementace algoritmu, která je následována odvozením časové složitosti a porovnáním s již existujícími přístupy. Na závěr je diskutována možnost dalšího pokračování projektu.
|
|
Algoritmus pro pevné body homomorfismů na slovech
Matocha, Vojtěch ; Holub, Štěpán (vedoucí práce) ; Žemlička, Jan (oponent)
V předložené práci studuji polynomiální algoritmus, který pro dané slovo rozhoduje, zda je pevným bodem nějakého netriviálního homomorfismu. Součástí práce je zpřesněný odhad složitosti, algoritmus v nejhorším případě pracuje v čase O(m · n), kde n značí délku slova a m velikost použité abecedy. V práci se dále zabývám problémem union-find, který je stěžejní součástí popisovaného algoritmu, a s odhadem jeho složitosti související Ackermannovou funkcí. V práci jsou shrnuty používané metody a důkazy jejich složitostí a je popsán postup, kterým lze řešit speciální případ union-find vyskytující se ve zkoumaném algoritmu. Následuje konkrétní implementace algoritmu, jejíž testovaná složitost odpovídá zpřesněnému odhadu. Součástí práce je také vizualizace chodu algoritmu na konkrétních vstupech.
|
|
Automatizace externí ekonomické analýzy podniku
Baroch, Václav ; Kyjonka, Vladimír (vedoucí práce) ; Král, Jaroslav (oponent)
Automatizované zpracování ekonomické analýzy podniku přináší jistá omezení. Klasická von Neumannova architektura doznala v poslední době určitých vylepšení, a je tak možné simulovat procesy, jejichž algoritmické zpracování bylo ještě před pár lety z praktického hlediska nemyslitelné, především kvůli nedostatečné početní a paměťové výkonnosti užívané IT technologie. Přes všechna zrychlení a razantní vylepšení IT technologií v posledních letech však softwarové zpracování simulace podnikových procesů naráží na dvě podstatná omezení, jež jsou popsána v práci. Je to nemožnost vytvářet izomorfní model reality a nutnost řešit simulaci interních a externích procesů v diskrétním čase.
|
|
Kombinatorika matematických struktur
Paták, Pavel
Kombinatorika matematické struktury prvního řádu je třída všech formulí, které platí ve všech strukturách v ní definovatelných. Tento pojem poprvé zavedl Krajíček v [6]. V předložené práci se zabýváme charakterizací a srovnáním kombinatorik známých matematických struktur (reálná a komplexní čísla, husté lineární uspořádání, …). Dále se věnujeme otázce výpočetní složitosti, tj. Otázce jak těžké je zjistit, zda daná formule leží v kombinatorice dané struktury. Dokážeme, že v případě modelů úplných teorií bez vlastností striktního uspořádání (SOP) či v případě pseudokonečných struktur je tento problém korekurzivně spočetně úplný, a tudíž algoritmicky neřešitelný.
|
|
Automatické umísťování uzlů v acyklickém orientovaném grafu do GUI
Juda, Jan ; Křivka, Zbyněk (oponent) ; Kolář, Dušan (vedoucí práce)
Cílem této práce je vytvořit aplikaci pro automatické rozmísťování uzlů v acyklických orientovaných grafech. Práce se především zaměřuje na pokročilé možnosti při tvorbě umístění uzlů, z kterých za zmínku stojí výběr polohy vybraných uzlů, rozdělení grafu na podgrafy či podporu polygonálních uzlů. V řešení jsou popsány vybrané algoritmy, které jsou použity ve výsledné aplikaci, a to konkrétně Fruchterman-Reingoldův silou orientovaný algoritmus, algoritmus Kamada-Kawai a algoritmus založený na Meyerových metodách samo-organizujících se grafů.
|
|
Comparison of Top trees implementations
Setnička, Jiří ; Majerech, Vladan (vedoucí práce) ; Mareš, Martin (oponent)
Porovnání implementací Top stromů - Abstrakt Jiří Setnička Definice a zavedení Top stromů a představení problémů, které se jimi dají efektivně řešit včetně problému hranové 2-souvislosti. Definice a zavedení topologických stromů, které jsou následně použity jako jeden z driverů pro Top stromy. Po úvodním seznámení s problematikou jsou představeny dvě implementace: jedna založená na samovyvažujících se stromech a druhá založená na topologických stromech. Porovnání obou imple- mentací je provedeno na dvou experimentech. Naměřené hodnoty jsou diskutovány v závěru - výsledky korespondují s úvodními odhady, ale s výrazně odlišnými multiplikativními konstantami, než bylo před- pokládáno. 1
|
|
Algoritmické problémy související s průnikovými grafy
Ivánek, Jindřich ; Pergel, Martin (vedoucí práce) ; Rytíř, Pavel (oponent)
V práci studujeme dva problémy pokrytí klikami, které mají zajímavé aplikace při reprezentaci tzv. k -bendovými průnikovými grafy: problém stupně pokrytí hran klikami a problém vrstevnatého pokrytí hran klikami. Zaměřujeme se na složitost těchto problémů a polynomiální algoritmy pro omezené třídy grafů. Hlavními výsledky práce je NP-úplnost problému vrstevnatého pokrytí hran klikami, polynomiální algoritmus pro tento problém na podtřídě grafů bez diamantů a také některé horní odhady pro konkrétní třídy grafů.
|
|
Kombinatorika matematických struktur
Paták, Pavel
Kombinatorika matematické struktury prvního řádu je třída všech formulí, které platí ve všech strukturách v ní definovatelných. Tento pojem poprvé zavedl Krajíček v [6]. V předložené práci se zabýváme charakterizací a srovnáním kombinatorik známých matematických struktur (reálná a komplexní čísla, husté lineární uspořádání, …). Dále se věnujeme otázce výpočetní složitosti, tj. Otázce jak těžké je zjistit, zda daná formule leží v kombinatorice dané struktury. Dokážeme, že v případě modelů úplných teorií bez vlastností striktního uspořádání (SOP) či v případě pseudokonečných struktur je tento problém korekurzivně spočetně úplný, a tudíž algoritmicky neřešitelný.
|